#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct AVLNode* AVLTree;
struct AVLNode {
    ElementType Data;
    AVLTree Left;
    AVLTree Right;
    int Height;
};

int GetHeight ( AVLTree BT ) {
    int HL, HR, MaxH;
    if ( BT ) {
        HL = GetHeight(BT->Left);
        HR = GetHeight(BT->Right);
        MaxH = HL > HR ? HL : HR;
        return (MaxH+1);
    } else return 0;
}

int Max ( int a, int b ) {
    return a > b ? a : b;
}

AVLTree Insert ( AVLTree T, ElementType X ) {
    if ( !T ) {
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->Data = X;
        T->Left = T->Right = NULL;
        T->Height = 1;
    } else if ( X < T->Data ) {
        T->Left = Insert( T->Left, X );
        if ( GetHeight( T->Left ) - GetHeight( T->Right ) == 2 )
            if ( X < T->Left->Data ) T = SingleLeftRotation(T);/*左单旋*/ 
            else T = DoublrLeftRightRotation(T);/*左-右双旋*/
        } else if ( X > T->Data ) {
            T->Right = Insert( T->Right, X );
            if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
                if ( X > T->Right->Data ) T = SingleRightRotation(T);/*右单旋*/
                else T = DoublrRightLeftRotation(T);/*右-左双旋*/
        }
    return T;
}
/*OK*/
AVLTree SingleLeftRotation ( AVLTree A ) {
    AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max(GetHeight(A->Left),GetHeight(A->Right))+1;
    B->Height = Max(GetHeight(B->Left),A->Height)+1;
    return B;
}
/*?*/
AVLTree SingleRightRotation ( AVLTree A ) {
    AVLTree B = A->Right;
    A->Right = B->Left;
    B->Left = A; 
    A->Height = Max(GetHeight(A->Left),GetHeight(A->Right))+1;
    B->Height = Max(GetHeight(B->Left),A->Height)+1;
    return B;
}
/*OK*/
AVLTree DoublrLeftRightRotation ( AVLTree A ) {
    A->Left = SingleRightRotation(A->Left);
    return SingleLeftRotation(A);
}
/*?*/
AVLTree DoublrRightLeftRotation ( AVLTree A ) {
    A->Right = SingleLeftRotation(A->Right);
    return SingleRightRotation(A);
}